CODE 14. Pascal's Triangle II

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2013/09/15/2013-09-15-CODE 14 Pascal's Triangle II/

访问原文「CODE 14. Pascal's Triangle II」

Given an index k,
return the kth row
of the Pascal’s triangle.
For example, given k =
3,
Return [1,3,3,1].
Note:
Could you optimize your algorithm to use only O(k)
extra space?

public ArrayList<Integer> getRow(int rowIndex) {
	// Start typing your Java solution below
	// DO NOT write main() function
	if (rowIndex < 0) {
		return new ArrayList<Integer>();
	}
	ArrayList<Integer> row = new ArrayList<Integer>();
	row.add(1);
	for (int i = 1; i <= rowIndex; i++) {
		ArrayList<Integer> tmpRow = new ArrayList<Integer>();
		tmpRow.add(1);
		for (int j = 1; j <= i; j++) {
			if (j == i) {
				tmpRow.add(1);
			} else {
				tmpRow.add(row.get(j) + row.get(j - 1));
			}
		}
		row.clear();
		row.addAll(tmpRow);
	}
	return row;
}